package com.zjj.algorithm.learning.leetcode.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成 中等题目
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * <p>
 * 示例 2：
 * 输入：n = 1
 * 输出：["()"]
 *
 * @author zjj_admin
 * @date 2022/11/11 16:40
 */
public class GenerateParentheses {


    public static void main(String[] args) {
        List<String> res = generateParenthesis(1);
        System.out.println("res = " + res);

    }


    /**
     * 时间
     * 1 ms
     * 击败
     * 76.87%
     * 内存
     * 41.6 MB
     * 击败
     * 35.39%
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(n, n, "", res);
        return res;
    }

    private static void dfs(int left, int right, String curStr, List<String> res) {
        // 左右括号都不剩余了，递归终止
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }
        // 如果左括号还剩余的话，可以拼接左括号
        if (left > 0) {
            dfs(left - 1, right, curStr + "(", res);
        }
        // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
        if (right > left) {
            dfs(left, right - 1, curStr + ")", res);
        }
    }
}
